// https://zhuanlan.zhihu.com/p/1913193150241042940

#include <bits/stdc++.h>
using namespace std;
using ll = ll;
pair<ll, ll> solve(ll a, ll b, ll c, ll d) {
  // 对于最小的 q, p 是唯一的
  ll n = a / b;
  a -= n * b;
  c -= n * d;
  if (c > d) {
    return make_pair(n + 1, 1);
  }
  auto res = solve(d, c, b, a);
  return make_pair(n * res.first + res.second, res.first);
}

int main() {
  int T;
  cin >> T;
  for (int t = 0; t < T; ++t) {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    assert(a > 0 && b > 0 && c > 0 && d > 0);
    // 替换 __int128 的比较方式
    assert(1.0 * a * d < 1.0 * c * b);
    cout << solve(a, b, c, d).second << '\n';
  }
  return 0;
}